/**
 * @author LKQ
 * @date 2021/12/4 10:50
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int x = 214;
        System.out.println(solution.mySqrt1(x));
        System.out.println(Math.pow(x, 0.5));
    }

    public int mySqrt(int x) {
        // 自己做的非正规二分查找
        long ans = 0;
        long temp = x;
        if (x == 1) {
            return 1;
        }
        for (long i = x/2; i >= 0;) {
            if (i * i == x) {
                ans = i;
                break;
            }else if (i * i > x){
                temp = i;
                i = i /2;
            }else if (i * i < x) {
                i = (i + temp) / 2;
            }
            if (i * i > x && (i-1) * (i-1) < x) {
                ans = i-1;
                break;
            }
            if (i * i < x && (i+1) * (i+1) > x) {
                ans = i;
                break;
            }
        }
        return (int)Math.floor(ans);
    }

    public int mySqrt1(int x) {
        // 正规的二分查找法
        int left = 0, right = x, ans = -1;
        while (left <= right) {
            int mid = (left + right ) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public int mySqrt2(int x) {
        // 牛顿迭代法
        if (x == 0) {
            return 0;
        }
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}
